package LK_Data_Structure;


class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
public class DataS_Day_7 {
    /*环形链表
    * 解题思路:快慢指针*/
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){

            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
                return true;
            }
        }
        return false;
    }
    /*合并俩个有序链表*/
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        /*没有创建头结点的做法*/
        ListNode newHead;
        ListNode tmp;
        if (list1 ==null){
            return list2;
        }
        if (list2 == null){
            return  list1;
        }
        if (list1.val <= list2.val){
            newHead=list1;
            tmp=list1;
            list1= list1.next;
        }else{
            newHead=list2;
            tmp=list2;
            list2= list2.next;
        }

        while (list1 !=null && list2 !=null){
            if (list1.val <= list2.val){
                tmp.next=list1;
                list1= list1.next;
                tmp=tmp.next;

            }else{
                tmp.next=list2;
                list2= list2.next;
                tmp=tmp.next;
            }
        }
        if (list1 !=null){
            tmp.next=list1;
        }
        if (list2 !=null){
            tmp.next=list2;
        }
        return newHead;

    }
    /*删除链表中所有等于val值的元素*/
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return null;
        }

        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == val) {
            head = head.next;
        }
        return head;
    }
}
